/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package primkruskaloptimo;

import java.util.ArrayList;
import java.util.Collections;

/**
 *
 * @author Diego Antonio Nuñez Cubas
 * cod: 0720144 - 2011-2
 */
public class Prim {

    ArrayList cola_vertices_candidatos = new ArrayList();//ESTE ARREGLO GUARDA LOS VERTIVCES Q SE PUEDEN ELEGIR
    int numero_vertives_arbol = 0;//INDICA EL NUMERO DE VERTICES INGRESADOS EN EL ARBOL DE CAMINO MINIMO
    int matriz_aristas[][];//ESTA MATRIZ GUARDA LA MATRIZ ORIGINAL
    int matriz_aristas_recorridas[][]; //ESTA MATRIZ GUARDA CON 1 LAS ARISTAS RECORRRIDAS, ADEMAS GUARDA CON -1 LAS ARISTAS QUE GENERAN CICLO
    int matriz_aristas_comprob_ciclos[][];  //ESTA MATRIZ GUARDA EL RECORRIDO DEL GRAFO BUSCANDO CICLOS
    private String cadena_ruta = "";
    private int suma_aristas = 0;

    public Prim(){}

    /*
     * ESTE CONSTRUCTOR INICIA LAS MATRICES CON SUS RESPECTIVOS VALORES INICIALES
     */
    public Prim(int _matriz_aristas[][], int num_vertices)
    {
        matriz_aristas = new int [num_vertices][num_vertices];
        matriz_aristas_recorridas = new int [num_vertices][num_vertices]; 
        matriz_aristas_comprob_ciclos = new int [num_vertices][num_vertices];
        
        for(int i = 0; i<matriz_aristas.length; i++)
        {
            for(int j = 0; j<matriz_aristas.length; j++)
            {
                if(i == j)
                {
                    matriz_aristas_recorridas[i][j] = -1;
                }
                else
                {
                    matriz_aristas_recorridas[i][j] = 0;
                }
            }
        }
        matriz_aristas = _matriz_aristas;
    }

    /*
     * ESTA ES LA FUNCION PRINCIPAL
     */
    public void ejecutarPrim()
    {
//        int num_vertices_recorridos = 0;
        int vertice_i = 0;
        int vertice_j = 0;
        int menor = 10000000;
        

        buscarAristaPesoMinimo(matriz_aristas);

        while( numero_vertives_arbol < matriz_aristas.length)
        {
            ordenarColaCandidatos();
//            imprimirVectorCandidatos();

            for(int i = 0; i < cola_vertices_candidatos.size(); i++)
            {
                for(int j = 0; j < matriz_aristas.length; j++)
                {
                    /*
                     * AQUI SE DETERMINA SI EL VERTICE PUEDE SER ELEGIDO O NO
                     */
                    if( esAristaElegible( Integer.parseInt(cola_vertices_candidatos.get(i).toString()) , j)
                        && matriz_aristas[Integer.parseInt(cola_vertices_candidatos.get(i).toString())][j]< menor
                        && matriz_aristas[Integer.parseInt(cola_vertices_candidatos.get(i).toString())][j]!=-123
                        )
                    {
                       /*
                        * AQUI SE EVALUA SI EL VERTICE ES EL MENOR DE TODAS LOS VERTICES ELEGIBLES
                        */
                        menor = matriz_aristas[Integer.parseInt(cola_vertices_candidatos.get(i).toString())][j];
                        vertice_i = Integer.parseInt(cola_vertices_candidatos.get(i).toString());
                        vertice_j = j;
                    }
                }
            }

            if( !existeCiclo( vertice_j, vertice_i ) )
            {
                matriz_aristas_recorridas[vertice_i][vertice_j] = matriz_aristas_recorridas[vertice_j][vertice_i] = 1;
                System.out.println("ARISTA ENTRA : "+vertice_i+"-"+vertice_j);
                System.out.println("ARISTA ENTRA : "+matriz_aristas[vertice_i][vertice_j]);
                setCadena_ruta(getCadena_ruta() + ", " + vertice_i + "-" + vertice_j);
                setSuma_aristas(getSuma_aristas() + matriz_aristas[vertice_i][vertice_j]);
                ingresarVerticeCandidato(vertice_i);
                ingresarVerticeCandidato(vertice_j);
                borrarMatriz();
            }
            else
            {
                matriz_aristas_recorridas[vertice_i][vertice_j] = matriz_aristas_recorridas[vertice_j][vertice_i] = -1;
                borrarMatriz();
            }

            menor = 10000000;
//            num_vertices_recorridos++;
            
        }
        
        imprimirMatriz(matriz_aristas_recorridas, "matriz_aristas_recorridas");
    }


    public void ordenarColaCandidatos()
    {
        Collections.sort(cola_vertices_candidatos);
    }

    /*
     * ESTE METODO DETERMINA SI EXISTE UN CICLO AL CONECTAR DOS VERTICES CON UNA ARISTA
     * PARA ELLO UTILIZA UNA FUNCION RECURSIVA QUE RECORRE TODAS LAS ARISTAS A PARTIR DE UN VERTICE
     */
    public boolean existeCiclo(int vertice_inicio, int vertice_comprobar)
    {
        boolean bandera_existe_ciclo = false;

        for (int i = 0; i< matriz_aristas_recorridas.length; i++)
        {
            if(bandera_existe_ciclo != true)
            {
                /*
                 * EN ESTE IF VERIFICA SI LA RUTA YA FUE TOMADA
                 */
                if(matriz_aristas_recorridas[vertice_inicio][i] == 1 && matriz_aristas_comprob_ciclos[i][vertice_inicio] != 1)
                {
                    matriz_aristas_comprob_ciclos[i][vertice_inicio] = matriz_aristas_comprob_ciclos[vertice_inicio][i] = 1;

                    if(i == vertice_comprobar)
                    {
                        bandera_existe_ciclo = true;
                    }
                    else
                    {
                        bandera_existe_ciclo = existeCiclo(i, vertice_comprobar);
                    }
                }
            }
        }
        return bandera_existe_ciclo;
    }

    
    public void imprimirMatriz(int matriz[][], String nombre_matriz)
    {
        System.out.println("NOMBRE MATRIZ : "+nombre_matriz);
        for(int i = 0; i< matriz.length; i++)
        {
            for(int j = 0; j< matriz.length; j++)
            {
                System.out.print(matriz[i][j]+"|");
            }
            System.out.println("");
        }
    }

    public void imprimirVectorCandidatos()
    {
        for(int i = 0 ; i< cola_vertices_candidatos.size(); i++)
        {
            System.out.println("CANDIDATO : "+cola_vertices_candidatos.get(i));
        }
    }

    public void borrarMatriz()
    {
        for(int i = 0; i< matriz_aristas_comprob_ciclos.length; i++)
        {
            for(int j = 0; j< matriz_aristas_comprob_ciclos.length; j++)
            {
                matriz_aristas_comprob_ciclos[i][j] = 0;
            }
        }
    }

    /*
     * ESTE METODO VERIFICA SI EL VERTICE PUEDE SER AGREGADO A LA COLA DE CANDIDATOS
     * DEPENDIENDO SI TIENE ARISTAS DISPONIBLES A ELEGIR
     */
    public void ingresarVerticeCandidato(int vertice)
    {
        boolean bandera_existe = false;
        int num_aristas_elegibles = 0;

        for(int i = 0; i< cola_vertices_candidatos.size(); i++)
        {
            matriz_aristas_recorridas[Integer.parseInt(cola_vertices_candidatos.get(i).toString())][vertice] = matriz_aristas_recorridas[vertice][Integer.parseInt(cola_vertices_candidatos.get(i).toString())] = -1;
        }

        for(int i = 0; i< cola_vertices_candidatos.size(); i++)
        {
            if(cola_vertices_candidatos.get(i).equals(vertice))
            {
                bandera_existe = true;
            }
        }

        for(int i = 0; i<matriz_aristas_recorridas.length; i++)
        {
            if(matriz_aristas_recorridas[vertice][i] == 0 && i!=vertice)
            {
                num_aristas_elegibles++;
            }
        }

        if(!bandera_existe /*&& num_aristas_elegibles!= 0*/)
        {
            cola_vertices_candidatos.add(vertice);
//            imprimirVectorCandidatos();
//            imprimirMatriz(matriz_aristas_recorridas, "matriz_aristas_recorridas");
            numero_vertives_arbol++;
        }

        else if(num_aristas_elegibles == 0)
        {
            boolean bandera = false;
            int k = 0;
            while (!bandera && k<=cola_vertices_candidatos.size())
            {
                try
                {
                    if(Integer.parseInt(cola_vertices_candidatos.get(k).toString()) == vertice)
                    {
                        bandera = true;
                        cola_vertices_candidatos.remove(k);
                    }
                
                }
                catch(Exception e)
                {
                    bandera = true;
                }
                k++;
            }
        }
    }


    public boolean esAristaElegible(int vertice_i, int vertice_j)
    {
        boolean bandera_elegible = true;

        if(matriz_aristas_recorridas[vertice_i][vertice_j] == 1 || matriz_aristas_recorridas[vertice_i][vertice_j] == -1)
        {
            bandera_elegible = false;
        }
        return bandera_elegible;
    }

    /*
     * ESTE METODO ENCUENTRA LA MENOR ARISTA DE MENOR PONDERACION
     * ADEMAS UBICA LOS VERTICES QUE CONECTA
     */
    public void buscarAristaPesoMinimo(int matriz[][])
    {
        int menor = 10000000;
        int indice_i = 0;
        int indice_j = 0;

        for(int i = 0; i < matriz.length; i++)
        {
            for(int j = 0; j<matriz.length; j++)
            {
                if(matriz[i][j] < menor && matriz[i][j] != -123)
                {
                    menor = matriz[i][j];
                    indice_i = i;
                    indice_j = j;
                }
            }
        }
        matriz_aristas_recorridas[indice_i][indice_j] = matriz_aristas_recorridas[indice_j][indice_i] = 1;
        setCadena_ruta(indice_i + "-" + indice_j);
        setSuma_aristas(getSuma_aristas() + matriz_aristas[indice_i][indice_j]);
        System.out.println("ARISTA ENTRA : "+indice_i+"-"+indice_j);
        ingresarVerticeCandidato(indice_i);
        ingresarVerticeCandidato(indice_j);
    }

    /**
     * @return the cadena_ruta
     */
    public String getCadena_ruta() {
        return cadena_ruta;
    }

    /**
     * @param cadena_ruta the cadena_ruta to set
     */
    public void setCadena_ruta(String cadena_ruta) {
        this.cadena_ruta = cadena_ruta;
    }

    /**
     * @return the suma_aristas
     */
    public int getSuma_aristas() {
        return suma_aristas;
    }

    /**
     * @param suma_aristas the suma_aristas to set
     */
    public void setSuma_aristas(int suma_aristas) {
        this.suma_aristas = suma_aristas;
    }
}
